/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***无向图，深度优先查找和广度优先查找            ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
#include <vector>
#include <list>
#include <string>

using std::cout;
using std::endl;
using std::list;
using std::string;
using std::vector;

class Graph
{
public:
    Graph() = delete;
    //输入节点的数量初始化一个图
    Graph(int n) : vertexVec(new vector<string>), edgeVec(new vector<vector<int>>(n, vector<int>(n, 0))),
                   isVisited(new vector<bool>(n, false)), numOfEdges(0)
    {
        vertexVec->reserve(n);
    }
    Graph(Graph &) = delete;
    Graph(Graph &&) = default;
    //添加节点
    void addVertex(string vertex)
    {
        vertexVec->push_back(vertex);
    }
    /*
    功能：添加边到二维矩阵中
    参数：v1 vertex的下标，v2 vertex的下标，
    返回值：
    */
    void addEdge(int v1, int v2, int weight)
    {
        //无向图需要添加两种路径
        (*edgeVec)[v1][v2] = weight;
        (*edgeVec)[v2][v1] = weight;
        numOfEdges++;
    }
    //获得边的数量
    int getEdgeNum()
    {
        return numOfEdges;
    }
    //获得节点的数量
    int getVertexNum()
    {
        return vertexVec->size();
    }
    //根据下标获得节点的名字
    string getVertexName(size_t i)
    {
        return (*vertexVec)[i];
    }
    //获得两个节点的权值
    int getWeight(const size_t &v1, const size_t &v2)
    {
        return (*edgeVec)[v1][v2];
    }
    void showGraph()
    {
        cout << "\t";
        for (const auto &item : (*vertexVec))
        {
            cout << item << "\t";
        }
        cout << endl;
        int i = 0;
        for (const auto &item : (*vertexVec))
        {
            cout << item << "\t";
            //输入一行
            for (const auto &item2 : ((*edgeVec)[i]))
            {
                cout << item2 << "\t";
            }
            cout << endl;
            i++;
        }
    }
    /*
    功能：返回与 下标为index结点  相邻的第一个坐标
    参数：index  需要查找元素的下标值
    返回值：如存在，返回与之相邻的第一个元素的下标，如不存在返回-1
    */
    int getFirstNeighbor(const size_t index)
    {
        auto len = vertexVec->size();
        for (size_t i = 0; i < len; i++)
        {
            if ((*edgeVec)[index][i] > 0)
            {
                return i;
            }
        }
        return -1;
    }
    /*
    功能：根据前一个邻接节点的下标，获取下一个邻接节点
    参数：v1 第一个节点的下标，v2 第二个节点的下标
    返回值：如存在，返回下标；如不存在，返回-1；
    */
    int getNextNeighbor(size_t v1, size_t v2)
    {
        auto count = vertexVec->size();
        for (size_t i = v2 + 1; i < count; i++)
        {
            if ((*edgeVec)[v1][i] > 0)
            {
                return i;
            }
        }
        return -1;
    }
    /*
    功能：深度优先遍历
    参数：start 深度优先遍历的开始节点  下标
    返回值：void  空   通过打印输出
    */
    void dfs(size_t start)
    {
        (*isVisited)[start] = true;
        // auto count=isVisited->size();
        // size_t i=0;
        auto firstNeighbor = getFirstNeighbor(start);
        cout << (*vertexVec)[start] << ">>";
        while (firstNeighbor != -1)
        {
            //第一个邻接点没有被访问过
            if (!(*isVisited)[firstNeighbor])
            {
                dfs(firstNeighbor);
                return;
            }
            //第一个邻接点已经被访问过
            firstNeighbor = getNextNeighbor(start, firstNeighbor);
        }
        dfs();
    }

    void dfs()
    {
        auto len = vertexVec->size();
        for (size_t i = 0; i < len; i++)
        {
            if (!(*isVisited)[i])
                dfs(i);
        }
    }
    void clearVisited()
    {
        for (auto item : (*isVisited))
        {
            item = false;
        }
    }
    /*
    功能：广度优先算法
    参数：传入的节点
    返回值： 空
    */
    void bfs(int index)
    {
        //先输出，并且加入队列
        cout << (*vertexVec)[index] << ">>";
        bfsList.push_back(index);
        (*isVisited)[index] = true;
        //队列非空时，从队头取出第一个值，进行深度变脸
        while (!bfsList.empty())
        {
            auto now = bfsList.front();
            bfsList.pop_front();
            //然后不断寻找now 的下一个邻接节点
            auto neighbor = getFirstNeighbor(now);
            while (neighbor != -1)
            {
                if (!(*isVisited)[neighbor])
                {
                    cout << (*vertexVec)[neighbor] << ">>";
                    bfsList.push_back(neighbor);
                    (*isVisited)[neighbor] = true;
                }
                neighbor = getNextNeighbor(now, neighbor);
            }
        }
    }

    void bfs()
    {
        size_t len = vertexVec->size();
        for (size_t i = 0; i < len; i++)
        {
            if (!(*isVisited)[i])
            {
                bfs(i);
            }
        }
        clearVisited();
        bfsList.clear();
    }

    //析构
    ~Graph()
    {
        if (vertexVec != nullptr)
        {
            delete vertexVec;
            vertexVec = nullptr;
        }
        if (edgeVec != nullptr)
        {
            delete edgeVec;
            edgeVec = nullptr;
        }
        if (isVisited != nullptr)
        {
            delete isVisited;
            isVisited = nullptr;
        }
    }

private:
    //节点名称集合，边的二维数组和边的数量
    vector<string> *vertexVec;
    vector<vector<int>> *edgeVec;
    //用于记录节点是否已经被访问，用于深度优先算法
    vector<bool> *isVisited;
    int numOfEdges;
    list<int> bfsList;
};

int main(int argc, char **argv)
{
    Graph *graph = new Graph(8);
    string vertexs = "12345678";
    for (size_t i = 0; i < vertexs.size(); i++)
    {
        graph->addVertex(string(1, vertexs[i]));
    }
    graph->addEdge(0, 1, 1);
    graph->addEdge(0, 2, 1);
    graph->addEdge(1, 3, 1);
    graph->addEdge(1, 4, 1);
    graph->addEdge(3, 7, 1);
    graph->addEdge(4,7,1);
    graph->addEdge(2,5,1);
    graph->addEdge(2,6,1);
    graph->showGraph();
    cout<<"深度优先结果："<<endl;
    graph->dfs();
    graph->clearVisited();
    cout<<endl;
    cout<<"广度优先结果："<<endl;
    graph->bfs();
    if (graph != nullptr)
    {
        delete graph;
        graph = nullptr;
    }
}